package code.cando;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * author : yeswater
 * date : 2023/12/7
 * <p>
 * 最长的有效括号  返回长度
 * 1 左括号开头 无效
 * 2 右括号开头 有效
 * 3 无效后左括号往后移 遍历
 */

public class T032 {

    public static void main(String[] args) {
        String str = "(()";
        String str1 = ")()())";
        String str2 = "()(()";
        // System.out.println(longestValidParentheses(str));
        // System.out.println(longestValidParentheses(str1));
        System.out.println(longestValidParentheses(str2));
    }

    /**
     * 双指针遍历记数 效率较低
     */
    public static int longestValidParentheses1(String s) {
        int res = 0;
        char[] chars = s.toCharArray();
        int length = chars.length;
        if (length <= 1) {
            return res;
        }
        for (int i = 0; i < length - 1; i++) { // 左指针
            int L = 0;
            int R = 0;

            if (chars[i] == ')') {
                continue;
            }

            L++;

            for (int j = i + 1; j < length; j++) { // 右指针
                if (L == R) {
                    res = Math.max(res, L * 2);
                }
                // 循环过程中 ) 比 ( 多,结束
                if (L < R) {
                    res = Math.max(res, L * 2);
                    break;
                }
                if (chars[j] == '(') {
                    L++;
                } else if (chars[j] == ')') {
                    R++;
                }
            }
            if (L == R) {
                res = Math.max(res, L * 2);
            }
        }
        return res;
    }

    /**
     * 栈
     */
    public static int longestValidParentheses2(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        int res = 0;
        int tmp = 0;
        for (char aChar : chars) {
            if (!stack.empty()) {
                if (stack.peek() == '(' && aChar == ')') {
                    stack.pop();
                    if (stack.empty() || stack.peek() == '(')
                    tmp += 2;
                    res = Math.max(res, tmp);
                }
                else if (stack.peek() == ')') {
                    stack.pop();
                    tmp = 0;
                } else {
                    stack.push(aChar);
                }
            }
            else if (aChar == '('){ // 第一个插入的是 (
                stack.push(aChar);
            } 
        }
        return res;
    }

    public static int longestValidParentheses(String s) {
        int res = 0;
        int start = 0;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push('(');
            }
            else {
                if (stack.empty()) {
                    res = Math.max(res, i - start);
                    start += 1;
                } else {
                    stack.pop();
                }
            }
        }
        
        if (stack.empty()) {
            return res;
        } else {
            return Math.max(res, s.length() - start - stack.size());
        }
    }

}
